package com.mzy.linear_struct.subject;

/**
 * @Author: codermzy
 * @Date: 2024/04/27/下午12:41
 * @Description:
 */
public class 排序链表148 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode sortList(ListNode head) {
            // 先找到链表的中点
            ListNode slow = head;
            ListNode fast = head;
            //     s
            // 4 2 1 3 6
            //         f
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            // 此时slow就是中点元素，head是头部元素，fast就是尾部元素
            // 对它进行归并排序
            mergeSort(head, fast);
            // mergeSort(slow.next, fast);

            return head;
        }

        private void mergeSort(ListNode left, ListNode right) {
            if (left == right) {
                return;
            }

            // 找中点
            ListNode mid = left;
            ListNode end = left;
            while (end != null && end.next != null) {
                mid = mid.next;
                end = end.next.next;
            }

            mergeSort(left, mid);
            mergeSort(mid.next, right);

            merge(left, mid, right);
        }

        private void merge(ListNode left, ListNode mid, ListNode right) {

        }
    }
}
